package warm100;

import utils.TreeNode;

public class diameterOfBinaryTree_543 {
    int maxV = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        diameter(root);
        return maxV-1;  //边等于节点数-1
    }
    public int diameter(TreeNode root) {
        //想法是维护一个最长直径节点个数，回溯返回左右子树最长直线节点个数
        if (root == null)
            return 0;
        int left=diameter(root.left);
        int right=diameter(root.right);
        maxV=Math.max(maxV , left+right+1 );  //维护最大长度
        return Math.max(left,right)+1;  //回溯到上一级时，返回连接着当前节点和左或右子树一条直线的长度
    }
}
